package demo8;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class PremutatioForBrackets {
    public PremutatioForBracketsImprove createPremutatioForBracketsImprove(){
        return new PremutatioForBracketsImprove();
    }
    public class PremutatioForBracketsImprove{
        private int pair;
        HashSet set = new HashSet<String>();
        public void premutationStart(int pair){
            this.pair=pair;
            // 0,2
            permutation(0,0,"");
        }
        /**
         *  count (every '(') and count(every ')') need equals  finally ,
         */
        public void permutation(int leftCount ,int rightCount ,String str){
            if(leftCount>pair || rightCount>pair){return;}
            // (()))
            if(leftCount<rightCount){
                return;
            }
            if(leftCount==rightCount && leftCount==pair){
                if(!set.add(str)){
                    System.out.println(str + " have been duplicated !");
                }else {
                    System.out.println(str);
                }

                return;
            }

            permutation(leftCount+1,rightCount,str+"(");
            permutation(leftCount,rightCount+1,str+")");
            return;

        }
    }

    /**
     * pair  is 3
     * char '(' ')'
     * List<></>
     * ()()
     * (())
     */
    public void premutationStart(int pair){
        // 0,2
        permutation(0,pair-1,"()");
    }
// 2
//(())
    private String insertChar(String str, int startIndex) {
        int endIndex=startIndex+1;
        String start = str.substring(0,startIndex+1);
        String end = str.substring(endIndex);
        return "("+start +end+")";

    }
    HashSet set = new HashSet<String>();

    public void permutation(int start ,int end ,String str){
        if(start==end){
            if(!set.add(str)){
                System.out.println(str + " have been duplicated !");
            }else{
                System.out.println(str);
            }
            return;
        }
        // insert () into  the nestest ()
        permutation(start,end-1,"()"+str);
        int startIndex = str.lastIndexOf(str);
        String center= insertChar(str, startIndex);
        // "(())"
        permutation(start,end-1,center);
        if(!("()"+str).equals(str+"()")){
            permutation(start,end-1,str+"()");
        }

    }

}
